home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 June / EnigmA AMIGA RUN 08 (1996)(G.R. Edizioni)(IT)[!][issue 1996-06][EARSAN CD VII].iso / earcd / gcc / ixemlsrc.lha / ixemul / ixnet / seq.c < prev    next >
C/C++ Source or Header  |  1996-03-13  |  8KB  |  322 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)seq.c       5.4 (Berkeley) 3/3/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #define KERNEL
  42. #include "ixnet.h"
  43. #include <sys/types.h>
  44. #include <errno.h>
  45. #include <db.h>
  46. #include <stdlib.h>
  47. #include "btree.h"
  48. #include "utils.h"
  49.  
  50. /*
  51.  *  _BT_SEQINIT -- Initialize a sequential scan on the btree.
  52.  *
  53.  *    Sets the tree's notion of the current scan location correctly
  54.  *    given a key and a direction.
  55.  *
  56.  *    Parameters:
  57.  *        t -- tree in which to initialize scan
  58.  *        key -- key for initial scan position
  59.  *        flags -- R_NEXT, R_PREV
  60.  *
  61.  *    Returns:
  62.  *        RET_SUCCESS, RET_ERROR, or RET_SPECIAL if there's no data
  63.  *        in the tree to scan.
  64.  *
  65.  *    Side Effects:
  66.  *        Changes current scan position for the tree.  Almost certainly
  67.  *        changes current page, as well.    Sets BTF_SEQINIT bit in tree
  68.  *        flags, so that we know we've initialized a scan.
  69.  */
  70.  
  71. int
  72. _bt_seqinit(t, key, flags)
  73.     BTREE_P t;
  74.     DBT *key;
  75.     int flags;
  76. {
  77.     BTITEM *item;
  78.     BTHEADER *h;
  79.     CURSOR *c;
  80.     IDATUM *id;
  81.     index_t last;
  82.  
  83.     /*
  84.      *  Figure out if we really have to search for the key that the
  85.      *  user supplied.  If key is null, then this is an unkeyed scan
  86.      *  and we can just start from an endpoint.
  87.      */
  88.  
  89.     c = &(t->bt_cursor);
  90.  
  91.     if (flags == R_CURSOR) {
  92.         if (key->data != (u_char *) NULL) {
  93.  
  94.             /* key supplied, find first instance of it */
  95.             item = _bt_first(t, key);
  96.             c->c_index = item->bti_index;
  97.             c->c_pgno = t->bt_curpage->h_pgno;
  98.         } else {
  99.             errno = EINVAL;
  100.             return (RET_ERROR);
  101.         }
  102.  
  103.     } else {
  104.  
  105.         /*
  106.          *  Unkeyed scan.  For backward scans, find the last item
  107.          *  in the tree; for forward scans, find the first item.
  108.          */
  109.  
  110.         if (_bt_getpage(t, (pgno_t) P_ROOT) == RET_ERROR)
  111.             return (RET_ERROR);
  112.         h = t->bt_curpage;
  113.         if (flags == R_LAST || flags == R_PREV) {
  114.  
  115.             /* backward scan */
  116.             while (!(h->h_flags & F_LEAF)) {
  117.                 last = NEXTINDEX(h) - 1;
  118.                 id = (IDATUM *) GETDATUM(h,last);
  119.                 if (_bt_getpage(t, id->i_pgno) == RET_ERROR)
  120.                     return (RET_ERROR);
  121.                 h = t->bt_curpage;
  122.             }
  123.  
  124.             /* skip empty pages */
  125.             while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE) {
  126.                 if (_bt_getpage(t, h->h_prevpg) == RET_ERROR)
  127.                     return (RET_ERROR);
  128.                 h = t->bt_curpage;
  129.             }
  130.  
  131.             c->c_pgno = h->h_pgno;
  132.             if (NEXTINDEX(h) > 0)
  133.                 c->c_index = NEXTINDEX(h) - 1;
  134.             else
  135.                 c->c_index = 0;
  136.         } else if (flags == R_FIRST || flags == R_NEXT) {
  137.             /* forward scan */
  138.             while (!(h->h_flags & F_LEAF)) {
  139.                 id = (IDATUM *) GETDATUM(h,0);
  140.                 if (_bt_getpage(t, id->i_pgno) == RET_ERROR)
  141.                     return (RET_ERROR);
  142.                 h = t->bt_curpage;
  143.             }
  144.  
  145.             /* skip empty pages */
  146.             while (NEXTINDEX(h) == 0 && h->h_nextpg != P_NONE) {
  147.                 if (_bt_getpage(t, h->h_nextpg) == RET_ERROR)
  148.                     return (RET_ERROR);
  149.                 h = t->bt_curpage;
  150.             }
  151.  
  152.             c->c_pgno = h->h_pgno;
  153.             c->c_index = 0;
  154.         } else {
  155.             /* no flags passed in */
  156.             errno = EINVAL;
  157.             return (RET_ERROR);
  158.         }
  159.     }
  160.  
  161.     /* okay, scan is initialized */
  162.     t->bt_flags |= BTF_SEQINIT;
  163.  
  164.     /* don't need the descent stack anymore */
  165.     while (_bt_pop(t) != P_NONE)
  166.         continue;
  167.  
  168.     if (c->c_index == NEXTINDEX(t->bt_curpage))
  169.         return (RET_SPECIAL);
  170.  
  171.     return (RET_SUCCESS);
  172. }
  173.  
  174. /*
  175.  *  _BT_SEQADVANCE -- Advance the sequential scan on this tree.
  176.  *
  177.  *    Moves the current location pointer for the scan on this tree one
  178.  *    spot in the requested direction.
  179.  *
  180.  *    Parameters:
  181.  *        t -- btree being scanned
  182.  *        flags -- for R_NEXT, R_PREV
  183.  *
  184.  *    Returns:
  185.  *        RET_SUCCESS, RET_ERROR, or RET_SPECIAL if there is no
  186.  *        more data in the specified direction.
  187.  *
  188.  *    Side Effects:
  189.  *        May change current page.
  190.  */
  191.  
  192. int
  193. _bt_seqadvance(t, flags)
  194.     BTREE_P t;
  195.     int flags;
  196. {
  197.     BTHEADER *h;
  198.     CURSOR *c;
  199.     index_t index;
  200.  
  201.     c = &(t->bt_cursor);
  202.     index = c->c_index;
  203.  
  204.     if (_bt_getpage(t, c->c_pgno) == RET_ERROR)
  205.         return (RET_ERROR);
  206.     h = t->bt_curpage;
  207.  
  208.     /* by the time we get here, don't need the cursor key anymore */
  209.     if (c->c_key != (char *) NULL)
  210.         (void) free(c->c_key);
  211.  
  212.     if (flags == R_NEXT) {
  213.  
  214.         /*
  215.          *  This is a forward scan.  If the cursor is pointing
  216.          *  at a virtual record (that is, it was pointing at
  217.          *  a record that got deleted), then we should return
  218.          *  the record it's pointing at now.  Otherwise, we
  219.          *  should advance the scan.  In either case, we need
  220.          *  to be careful not to run off the end of the current
  221.          *  page.
  222.          */
  223.  
  224.         if (c->c_flags & CRSR_BEFORE) {
  225.  
  226.             if (index >= NEXTINDEX(h)) {
  227.                 /* out of items on this page, get next page */
  228.                 if (h->h_nextpg == P_NONE) {
  229.                     /* tell caller we're done... */
  230.                     c->c_index = NEXTINDEX(h);
  231.                     return (RET_SPECIAL);
  232.                 }
  233.  
  234.                 /* skip empty pages */
  235.                 do {
  236.                     if (_bt_getpage(t, h->h_nextpg)
  237.                         == RET_ERROR) {
  238.                         c->c_index = NEXTINDEX(h);
  239.                         return (RET_ERROR);
  240.                     }
  241.                     h = t->bt_curpage;
  242.                     c->c_pgno = h->h_pgno;
  243.                 } while (NEXTINDEX(h) == 0
  244.                      && h->h_nextpg != P_NONE);
  245.  
  246.                 if (NEXTINDEX(h) == 0) {
  247.                     /* tell caller we're done */
  248.                     c->c_index = NEXTINDEX(h);
  249.                     return (RET_SPECIAL);
  250.                 }
  251.                 index = 0;
  252.             }
  253.             c->c_flags &= ~CRSR_BEFORE;
  254.  
  255.         } else if (++index >= NEXTINDEX(h)) {
  256.  
  257.             /* out of items on this page, get next page */
  258.             if (h->h_nextpg == P_NONE) {
  259.                 /* tell caller we're done... */
  260.                 c->c_index = NEXTINDEX(h);
  261.                 return (RET_SPECIAL);
  262.             }
  263.  
  264.             /* skip empty pages */
  265.             do {
  266.                 if (_bt_getpage(t, h->h_nextpg) == RET_ERROR) {
  267.                     c->c_index = NEXTINDEX(h);
  268.                     return (RET_ERROR);
  269.                 }
  270.                 h = t->bt_curpage;
  271.                 c->c_pgno = h->h_pgno;
  272.             } while (NEXTINDEX(h) == 0 && h->h_nextpg != P_NONE);
  273.  
  274.             if (NEXTINDEX(h) == 0) {
  275.                 /* tell caller we're done */
  276.                 c->c_index = NEXTINDEX(h);
  277.                 return (RET_SPECIAL);
  278.             }
  279.             index = 0;
  280.         }
  281.     } else if (flags == R_PREV) {
  282.  
  283.         /* for backward scans, life is substantially easier */
  284.         c->c_flags &= ~CRSR_BEFORE;
  285.         if (c->c_key != (char *) NULL) {
  286.             (void) free(c->c_key);
  287.             c->c_key = (char *) NULL;
  288.         }
  289.  
  290.         if (index == 0) {
  291.  
  292.             /* we may be done */
  293.             c->c_index = 0;
  294.  
  295.             /* out of items on this page, get next page */
  296.             if (h->h_prevpg == P_NONE)
  297.                 return (RET_SPECIAL);
  298.  
  299.             /* skip empty pages */
  300.             do {
  301.                 if (_bt_getpage(t, h->h_prevpg) == RET_ERROR)
  302.                     return (RET_ERROR);
  303.                 h = t->bt_curpage;
  304.                 c->c_pgno = h->h_pgno;
  305.             } while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE);
  306.  
  307.             if (NEXTINDEX(h) == 0)
  308.                 return (RET_SPECIAL);
  309.  
  310.             index = NEXTINDEX(h) - 1;
  311.         } else
  312.             --index;
  313.     } else {
  314.         /* must specify a direction */
  315.         errno = EINVAL;
  316.         return (RET_ERROR);
  317.     }
  318.  
  319.     c->c_index = index;
  320.     return (RET_SUCCESS);
  321. }
  322.